package com.atguigui.leetcode1;

/**
 * 1186. 删除一次得到子数组最大和
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/6/27 8:58
 */
public class P1186MaximumSubarraySumWithOneDeletion {
    public static void main(String[] args) {
        Solution solution = new P1186MaximumSubarraySumWithOneDeletion().new Solution();
        int[] arr = {1, -2, 0, 3};
        solution.maximumSum(arr);
    }

    class Solution {
        public int maximumSum(int[] arr) {
            int ans = arr[0];
            int n = arr.length;
            // 二维dp，第二维度表示是否进行删除
            int[][] dp = new int[n][2];
            dp[0][0] = arr[0];  // 初始化0位，表示不删除数值；1位表示删除数据，默认为0
            for (int i = 1; i < n; i++) {
                // 要么删除当前arr[i]，只取到前位和；要么删除前面的，只取arr[i]
                dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + arr[i]);   // 删除1次
                // 前面的不删除和0比，小于0直接弃掉
                dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];              // 删除0次
                // 循环到最后是做了删除的大还是不做删除的大
                ans = Math.max(Math.max(dp[i][0], dp[i][1]), ans);
            }
            return ans;
        }
    }
}
